package stmo.链表;


/**
 *  约瑟夫问题
 */

public class JosephTest {

    public static void main(String[] args) {

        //构建循环链表，包含41个结点，分别存储1~41之间的值
        Node head = new Node(null,null);
        Node pre = head;
        for (int i = 1;i <= 41;i++) {
            Node newNode = new Node(i,null);
            pre.next = newNode;
            pre = pre.next;
        }
        pre.next = head.next;


        //需要count计数器，模拟报数
        int count = 0;
        //遍历循环链表
        pre = head;
        while (pre != pre.next) {
            count++;
            if (count == 3) {
                System.out.print(pre.next.item+",");
                pre.next = pre.next.next;
                count = 1;
            }
            pre = pre.next;
        }
        System.out.println(pre.item);



        //构建循环链表，包含41个结点，分别存储1~41之间的值
        head = new Node(null,null);
        pre = head;
        for (int i = 1;i <= 41;i++) {
            Node newNode = new Node(i,null);
            pre.next = newNode;
            pre = pre.next;
        }
        pre.next = head.next;


        //需要count计数器，模拟报数
        count = 0;
        Node first = head.next;
        Node before = null;
        while (first != first.next) {
            count++;
            if(count == 3) {
                before.next = first.next;
                System.out.print(first.item+",");
                count = 0;
                first = first.next;
            }else {
                before = first;
                first = first.next;
            }
        }
        System.out.println(first.item);

    }



    //内部结点类
    private static class Node<T> {

        T item;

        Node next;

        public Node(T item,Node next) {

            this.item = item;
            this.next = next;
        }
    }
}
